/*
 * @(#)Sierpinski.java	1.0 Apr 26, 2008
 *
 *	The MIT License
 *
 *	Copyright (c) 2008 Malachi de AElfweald <malachid@gmail.com>
 *
 *	Permission is hereby granted, free of charge, to any person obtaining a copy
 *	of this software and associated documentation files (the "Software"), to deal
 *	in the Software without restriction, including without limitation the rights
 *	to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 *	copies of the Software, and to permit persons to whom the Software is
 *	furnished to do so, subject to the following conditions:
 *
 *	The above copyright notice and this permission notice shall be included in
 *	all copies or substantial portions of the Software.
 *
 *	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 *	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 *	FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 *	AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 *	LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 *	OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 *	THE SOFTWARE.
 */
package org.eoti.math;

import java.util.*;

public class Sierpinski
{
	// test
	public static void main(String[] args)
			throws Exception
	{
		int max = Integer.parseInt(args[0]);
		System.out.println("We think line#"+max+" should look like: " + toBinaryString(getLine(max)));
		System.out.println("Let's find out:");
		ArrayList<BitSet> lines = getRows(max);
		String s = ""+max;
		String fmt = "%"+s.length()+"d: %s\n";

		for(int i=0; i<lines.size(); i++)
			System.out.format(fmt, i, toBinaryString(lines.get(i)));

		System.out.println("");
	}

	public static String toBinaryString(BitSet line)
	{
		StringBuilder sb = new StringBuilder();
		for(int pos=0; pos<line.length(); pos++)
			sb.append( (line.get(pos)?"1":"0") );

		return sb.toString();
	}

	public static ArrayList<BitSet> getRows(int lastLineInclusive)
	{
		ArrayList<BitSet> list = new ArrayList<BitSet>(lastLineInclusive);
		BitSet current = new BitSet();
		current.set(0);
		list.add(current);

		for(int line=1; line<=lastLineInclusive; line++)
		{
			current = nextLine(current);
			list.add(current);
		}

		return list;
	}

	protected static int closestFullLine(int lineNumber)
	{
		/**
		 * 0: 1
		 * 1: 11
		 * 2: 101
		 * 3: 1111
		 * 4: 10001
		 *
		 * all 1s are on lines 0,1,3,7,15
		 * or specifically, all (2^n) 1s on 2^n-1
		 *
		 * highestOneBit returns 0 for 0, or binary value for leftmost position
		 * 0: 0
		 * 1: 1
		 * 2: 10: 2
		 * 3: 11: 2
		 * 4: 100: 4
		 * 5: 101: 4
		 * etc
		 *
		 * so, for line x, previous all-1s is at highestOneBit(x)-1
		 */

		if(lineNumber <= 1) // lineNumber = 0, 1
			return lineNumber;

		int last = Integer.highestOneBit(lineNumber) - 1;
		if(last == lineNumber) // lineNumber = 3,7,15, etc
			return lineNumber;

		int next = last*2+1; // (last,next) = (3,7), (7,15), etc

		/**
		 * lineNumber = 4
		 * if((4 - 3) < (7 - 4))
		 * if(1 < 3)
		 * return 3
		 */
		if((lineNumber - last) < (next - lineNumber))
			return last;

		/**
		 * lineNumber = 6
		 * if((6-3) < (7-6))
		 * if(3 < 1)
		 * return 7
		 */
		return next;
	}

	public static BitSet getLine(int lineNumber)
	{
		// get nearest line of all 1s
		int closestLine = closestFullLine(lineNumber);

		/**
		 * closestLine = 2^n-1
		 * but BitSet should be 2^n
		 * ie: line 3 = 1111 (4-1s)
		 * and:line 7 = 11111111 (8-1s)
		 * closestLine+1 for BitSet
		 */
		BitSet current = new BitSet(closestLine+1);
		current.set(0, closestLine+1);// 0-based line 3 has 4-1s, line 7 has 8-1s, etc

		/**
		 * if they requested getLine(3)
		 * and current = "1111" (ie: line3)
		 * then return it
		 */
		if(closestLine == lineNumber)
			return current;

		/**
		 * lineNumber: 4
		 * current starts as 3 (2^n-1)
		 * current.length starts as 4 (2^n)
		 * technically, currentLineNumber = current.length()-1 [0-based]
		 * so, while (current.length()-1) != lineNumber
		 *
		 * lineNumber: 6
		 * current starts as 7 (2^n-1)
		 * current.length starts as 8 (2^n)
		 * technically, currentLineNumber = current.length()-1 [0-based]
		 * so, while (current.length()-1) != lineNumber
		 */
		while( (current.length()-1) != lineNumber)
		{
			if(closestLine < lineNumber)
				current = nextLine(current);
			else
				current = previousLine(current);
		}

		return current;
	}

	protected static BitSet nextLine(BitSet previousLine)
	{
		int prevLength = previousLine.length();
		BitSet nextLine = new BitSet(prevLength + 1);
		for(int pos=0; pos<=prevLength; pos++)
		{
			boolean aboveLeft = (pos != 0 && previousLine.get(pos - 1));
			boolean above = (pos != prevLength && previousLine.get(pos));
			nextLine.set(pos, aboveLeft ^ above);
		}
		return nextLine;
	}

	protected static BitSet previousLine(BitSet nextLine)
	{
		int nextLength = nextLine.length();
		BitSet prevLine = new BitSet(nextLength - 1);
		for(int pos=0; pos<nextLength; pos++)
		{
			boolean left = (pos != 0 && prevLine.get(pos - 1));
			boolean below = nextLine.get(pos);
			prevLine.set(pos, left ^ below);
		}
		return prevLine;
	}
}
